#include <iostream>
#include <cmath>

/* 手电筒过河问题
 * 多个小朋友晚上过河，桥最多通过2人，只有一个手电筒，每次过河时间由两人中较长时间决定
 * 求所有小朋友通过的最小时间
 */

float getCrossRiverTime(const float* cross_time, int person_num)
{
  if (person_num == 0 || cross_time == nullptr) {
    return 0;
  }
  if (person_num <= 2) {
    return cross_time[person_num - 1];
  }

  float f_i_2 = cross_time[0];
  float f_i_1 = cross_time[1];
  float f_i = f_i_1;
  for (int i = 2; i < person_num; ++i) {
    float f_1 = f_i_1 + cross_time[0] + cross_time[i];
    float f_2 = f_i_2 + cross_time[0] + cross_time[i] + 2 * cross_time[1];
    std::cout << f_1 << ",\t" << f_2 << ":\t";
    if (f_1 < f_2) {
      f_i = f_1;
      std::cout << i << " choose_1 " << i - 1 << std::endl;
    } else {
      f_i = f_2;
      std::cout << i << " choose_2 " << i - 2 << std::endl;
    }

    f_i_2 = f_i_1;
    f_i_1 = f_i;
  }
  
  return f_i;
}

int main()
{
  // float cross_time[] = {1, 2, 5, 10, 15};
  float cross_time[] = {1, 1.2, 2.1, 2.2, 2.3};
  int person_num = sizeof(cross_time) / sizeof(cross_time[0]);

  std::cout << getCrossRiverTime(cross_time, person_num) << std::endl;

  return 0;
}

